package org.example.struct.array2;

/**
 * @author liyishan
 * @date 2023/10/18 13:35
 * @apiNote
 */

public class Test00835LargestOverlap {

    public static void main(String[] args) {
        int[][] img1 = {{1, 1, 0, 0, 1}, {1, 0, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 0, 0}, {1, 0, 0, 0, 0}};
        int[][] img2 = {{1, 1, 0, 0, 1}, {1, 0, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 0, 0}, {1, 0, 0, 0, 0}};
        System.out.println(test(img1, img2));
    }

    public static int test(int[][] img1, int[][] img2) {
        int n = img1.length;
        int[][] count = new int[2 * n + 1][2 * n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (img1[i][j] == 1) {
                    for (int i2 = 0; i2 < n; i2++) {
                        for (int j2 = 0; j2 < n; j2++) {
                            if (img2[i2][j2] == 1) {
                                count[i - i2 + n][j - j2 + n] += 1;
                            }
                        }
                    }
                }
            }
        }
        int ans = 0;
        for (int[] row : count) {
            for (int r : row) {
                ans = Math.max(ans, r);
            }
        }
        return ans;
    }
}
